package maximumDeletionsOnAString_2430;

import java.util.Arrays;

//https://leetcode.cn/problems/maximum-deletions-on-a-string/
public class Solution {
    public static int deleteString(String s) {
        int[][] lcp = new int[s.length() + 1][s.length() + 1];
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = s.length() - 1; j >= 0; j--) {
                if (s.charAt(i) == s.charAt(j)) {
                    lcp[i][j] = lcp[i][j] = lcp[i + 1][j + 1] + 1;
                } else {
                    lcp[i][j] = 0;
                }
            }
        }
        int[] dp = new int[s.length()];
        // 如果存在向左偏移 k 个似的
        for (int i = dp.length - 1; i >= 0; i--) {
            for (int j = 1; j + i < dp.length; j++) {
                if (lcp[i][j+i] >= j) {
                    dp[i] = Math.max(dp[i + j], dp[i]);
                }
            }
            dp[i]++;
        }
        return dp[0];
    }

    public static void main(String[] args) {
        System.out.println(deleteString("aaaaa"));
    }
}
